package heimaKaoshi;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

//力扣刷题
class Solution {
    /**力扣刷题
     * 88. 合并两个有序数组
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
//      System.arraycopy(nums2, 0, nums1, m,n);
//      Arrays.sort(nums1);
        //2解法2-逆向双指针，不需要额外空间
        int p = m + n - 1;
        int p1 = m - 1;
        int p2 = n - 1;
        int cur; //当前位置需要放置的元素
        while (p1 >= 0 || p2 >= 0) {
            if (p1 == -1) {
                cur = nums2[p2];
                nums1[p] = cur;
                p2--;
                p--;
            } else if (p2 == -1) {
                cur = nums1[p1];
                nums1[p] = cur;
                p1--;
                p--;
            } else {
                if (nums1[p1] > nums2[p2]) {
                    cur = nums1[p1];
                    nums1[p] = cur;
                    p1--;
                    p--;
                } else {
                    cur = nums2[p2];
                    nums1[p] = cur;
                    p2--;
                    p--;
                }
            }
        }
    }

    /**
     * 27. 移除元素  --也是可以看成双指针
     * @param nums
     * @param val
     * @return
     */
    public int removeElement(int[] nums, int val) {
        int k = 0; //// 新数组的长度
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] != val) {
                // 把不等于val的元素放到新数组中
                nums[k] = nums[i];
                k++;
            }
        }
       return k;
    }

    //26. 删除有序数组中的重复项  ---快慢指针
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        //双指针
        //快指针表示遍历数组到达的下标位置，慢指针表示下一个不同元素要填入的下标位置，初始时两个指针都指向下标 1
        int fast =1,slow = 1;
        for(;fast<nums.length;fast++) {
            if(nums[fast] != nums[fast-1]) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }
    //80.删除有序数组中的重复项 II
    public int removeDuplicates_1(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length <= 2) {
            return nums.length;
        }
        //slow始终是最后一个不重复元素的后一个位置 也是不重复元素个数
        int k= 2; //最多可以删除k个重复的元素
        int fast =k,slow = k;
        for(;fast<nums.length;fast++) {
            if(nums[slow-2] != nums[fast]) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }

    /**
     * 169. 多数元素 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
     * @param nums
     * @return
     */
    //1 <= n <= 5 * 104
    public int majorityElement(int[] nums) {
        if(nums.length < 2) {
            return nums[0];
        }
        Map<Integer,Integer> countMap = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            if(countMap.containsKey(nums[i])) {
                countMap.put(nums[i],countMap.get(nums[i])+1);
            } else {
                countMap.put(nums[i],1);
            }
        }
        for(Map.Entry<Integer,Integer> entry : countMap.entrySet()) {
            if(entry.getValue() > nums.length/2) {
                return entry.getKey();
            }
        }
        return -1;

    }

    // 189轮转数组
    //给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
    public void rotate(int[] nums, int k) {
        //取余  额外开辟数组
        int[] copy = new int[nums.length];
        for(int i = 0; i < nums.length; i++) {
            copy[(i+k)%nums.length] = nums[i];
        }
        for(int i = 0; i < nums.length; i++) {
            nums[i] = copy[i];
        }
        //这行代码的意思是将 nums 数组从索引 0 开始的 nums.length 个元素复制到 copy 数组的索引 0 开始的位置
        //System.arraycopy(nums, 0, copy, 0,nums.length);
    }

    //121. 买卖股票的最佳时机
/*    我们需要找出给定数组中两个数字之间的最大差值
    （即，最大利润）。此外，第二个数字（卖出价格）必须大于第一个数字（买入价格*/
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }
        int minPrice = prices[0];
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            } else {
                maxProfit = Math.max(maxProfit, prices[i] - minPrice);
            }
        }
        return maxProfit;
    }
    //122. 买卖股票的最佳时机 II
    public int maxProfit_1(int[] prices) {
        //贪心算法只能用于计算最大利润，计算的过程并不是实际的交易过程。
        //贪心算法：所以部分正收益之和就是最大收益
        int maxProfit = 0;
        for(int i = 1; i < prices.length; i++) {
            if(prices[i] > prices[i-1]) {
                maxProfit += prices[i] - prices[i-1];
            }
        }
        return maxProfit;
    }

    //55. 跳跃游戏
    public boolean canJump(int[] nums) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        if (nums.length == 1) {
            return true;
        }
        // 贪心算法
/*        int n = nums.length;
        //当前可以到达最远位置下标
        int rightmost = 0;
        for (int i = 0; i < n; ++i) {
            if (i <= rightmost) {
                //当前位置可以到达的最远位置下标
                rightmost = Math.max(rightmost, i + nums[i]);
                if (rightmost >= n - 1) {
                    return true;
                }
            }
        }
        return false;*/
        //反过来想 从最后一个位置是否可以到第一个位置
        int n = nums.length;
        int leftmost = n - 1;
        for(int i= n-2; i >= 0; i--) {
            //该点可达 标记为绿色
            if(i + nums[i] >= leftmost) {
                leftmost = i;
            }
        }
        return  leftmost == 0;
    }
    //45. 跳跃游戏 II
    public int jump(int[] nums) {
        int position = nums.length - 1;
        int steps = 0;
        while (position > 0) {
            for (int i = 0; i < position; i++) {
                if (i + nums[i] >= position) {
                    position = i;
                    steps++;
                    break;
                }
            }
        }
        return steps;
    }

}
